home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / portablc.zip / FILECMPR.C < prev    next >
Text File  |  1990-01-29  |  17KB  |  482 lines
  1. /*************************************************************************
  2.         filecmpr.c     : Compresses both ASCII and Binary Files
  3.  
  4. Originally secured from a DOS Bulletin Board. This is totally free Shareware.
  5. Changed much of the original Dos file to work under Unix/Xenix System 5;
  6. Cleaned up the code to make it more readable and maintainable;
  7. Added logic to allow decompressing a file onto itself & added many edits;
  8. I attached original author documentation below of the original program.
  9. Note that this program was originally secured for use with the upload/down-
  10. load system, however, anyone can use this to compress/uncompress any file.
  11. This also has been tested under DOS using Microsoft Version 5.1.
  12.  
  13.         12/8/89 Martin Katz
  14.  
  15. **************************************************************************
  16.     Original Author Documention:
  17.  
  18.         LZSS.C -- A Data Compression Program
  19.  
  20.         4/6/1989 Haruhiko Okumura
  21.         Use, distribute, and modify this program freely.
  22.         Please send me your improved versions.
  23.                 PC-VAN          SCIENCE
  24.                 NIFTY-Serve     PAF01022
  25.                 CompuServe      74050,1022
  26.  
  27. The algorithm is quite simple:
  28. Keep a ring buffer, which initially contains "space" characters
  29. only.  Read several letters from the file to the buffer.  Then search
  30. the buffer for the longest string that matches the letters just read,
  31. and send its length and position in the buffer.
  32.  
  33. If the buffer size is 4096 bytes, the position can be encoded in 12
  34. bits.  If we represent the match length in four bits, the <position,
  35. length> pair is two bytes long.  If the longest match is no more than
  36. two characters, then we send just one character without encoding, and
  37. restart the process with the next letter.  We must send one extra bit
  38. each time to tell the decoder whether we are sending a <position,
  39. length> pair or an unencoded character.
  40.  
  41. The accompanying file LZSS.C is a version of this algorithm.  This
  42. implementation uses multiple binary trees to speed up the search for the
  43. longest match.  All the programs in this article are written in
  44. draft-proposed ANSI C.  I tested them with Turbo C 2.0.
  45.  
  46. *************************************************************************/
  47.  
  48. #include <stdio.h>
  49. #include <string.h>
  50. #include <ctype.h>
  51.  
  52. #define N 4096                                  /* size of ring buffer */
  53. #define F 18                                    /* upper limit for match_length */
  54. #define THRESHOLD 2             /* encode string into position and length
  55.                                                                    if match_length is greater than this */
  56.  
  57. #define NIL N                  /* index for root of binary search trees */
  58.  
  59. #ifdef TWO60
  60. #define CLEAR  printf("\033X")
  61. #else
  62. #define CLEAR  printf("\033[H\033[2J\n")
  63. #endif
  64.  
  65. #define BELL printf("\007\n")
  66.  
  67. unsigned long int textsize = 0,   /* text size counter */
  68.                                   codesize = 0,   /* code size counter */
  69.                 printcount = 0; /* counter reporting progress every 1K bytes*/
  70.  
  71. unsigned char text_buf[N + F - 1]; /* ring buffer of size N, with extra F-1
  72.                                                                         bytes to facilitate string comparison */
  73.  
  74. int match_position, match_length,  /* of longest match.  These are set by the
  75.                                                                         InsertNode() procedure. */
  76.     lson[N + 1], rson[N + 257], dad[N + 1];  /* left & right children & parents,
  77.                                                                                 These constitute binary search trees. */
  78.  
  79. FILE *infile, *outfile;                         /* input & output files */
  80.  
  81.  
  82. void InitTree()  /* initialize trees */
  83. {
  84.         int  i;
  85.  
  86.                         /* For i = 0 to N - 1, rson[i] and lson[i] will be the right and
  87.                         left children of node i.  These nodes need not be initialized.
  88.                         Also, dad[i] is the parent of node i.  These are initialized to
  89.                         NIL (= N), which stands for 'not used.'
  90.                         For i = 0 to 255, rson[N + i + 1] is the root of the tree
  91.                         for strings that begin with character i.  These are initialized
  92.                         to NIL.  Note there are 256 trees. */
  93.  
  94.         for (i = N + 1; i <= N + 256; i++)
  95.                 rson[i] = NIL;
  96.  
  97.         for (i = 0; i < N; i++)
  98.                 dad[i] = NIL;
  99. }
  100.  
  101. void InsertNode(r)
  102.         int r;
  103.  
  104.         /* Inserts string of length F, text_buf[r..r+F-1], into one of the
  105.            trees (text_buf[r]'th tree) and returns the longest-match position
  106.            and length via the global variables match_position and match_length.
  107.            If match_length = F, then removes the old node in favor of the new
  108.            one, because the old one will be deleted sooner.
  109.            Note r plays double role, as tree node and position in buffer. */
  110.  
  111. {
  112.         int  i, p, cmp;
  113.         unsigned char  *key;
  114.  
  115.         cmp = 1;
  116.         key = &text_buf[r];
  117.         p = N + 1 + key[0];
  118.         rson[r] = lson[r] = NIL;
  119.         match_length = 0;
  120.  
  121.         for ( ; ; )
  122.         {
  123.                 if (cmp >= 0)
  124.                 {
  125.                         if (rson[p] != NIL)
  126.                                 p = rson[p];
  127.                         else
  128.                         {
  129.                                 rson[p] = r;
  130.                                 dad[r] = p;
  131.                                 return;
  132.                         }
  133.                 }
  134.                 else
  135.                 {
  136.                         if (lson[p] != NIL)
  137.                                 p = lson[p];
  138.                         else
  139.                         {
  140.                                 lson[p] = r;
  141.                                 dad[r] = p;
  142.                                 return;
  143.                         }
  144.                 }
  145.  
  146.                 for (i = 1; i < F; i++)
  147.                         if ((cmp = key[i] - text_buf[p + i]) != 0)
  148.                                 break;
  149.  
  150.                 if (i > match_length)
  151.                 {
  152.                         match_position = p;
  153.                         if ((match_length = i) >= F)
  154.                                 break;
  155.                 }
  156.         }
  157.  
  158.         dad[r] = dad[p];
  159.         lson[r] = lson[p];
  160.         rson[r] = rson[p];
  161.         dad[lson[p]] = r;
  162.         dad[rson[p]] = r;
  163.  
  164.         if (rson[dad[p]] == p)
  165.                 rson[dad[p]] = r;
  166.         else
  167.                 lson[dad[p]] = r;
  168.  
  169.         dad[p] = NIL;  /* remove p */
  170. }
  171.  
  172.  
  173. void DeleteNode(p)  /* deletes node p from tree */
  174.         int p;
  175. {
  176.         int q;
  177.  
  178.         if (dad[p] == NIL)
  179.                 return;  /* not in tree */
  180.  
  181.         if (rson[p] == NIL)
  182.                 q = lson[p];
  183.         else if (lson[p] == NIL)
  184.                 q = rson[p];
  185.         else
  186.         {
  187.                 q = lson[p];
  188.                 if (rson[q] != NIL)
  189.                 {
  190.                         do
  191.                         {
  192.                                 q = rson[q];
  193.                         }
  194.                         while (rson[q] != NIL);
  195.  
  196.                         rson[dad[q]] = lson[q];
  197.                         dad[lson[q]] = dad[q];
  198.                         lson[q] = lson[p];
  199.                         dad[lson[p]] = q;
  200.                 }
  201.                 rson[q] = rson[p];
  202.                 dad[rson[p]] = q;
  203.         }
  204.  
  205.         dad[q] = dad[p];
  206.  
  207.         if (rson[dad[p]] == p)
  208.                 rson[dad[p]] = q;
  209.         else
  210.                 lson[dad[p]] = q;
  211.  
  212.         dad[p] = NIL;
  213. }
  214.  
  215.  
  216. void Encode()
  217. {
  218.         int  i, c, len, r, s, last_match_length, code_buf_ptr;
  219.         unsigned char  code_buf[17], mask;
  220.  
  221.         InitTree();  /* initialize trees */
  222.  
  223.         code_buf[0] = 0;  /* code_buf[1..16] saves eight units of code, and
  224.                 code_buf[0] works as eight flags, "1" representing that the unit
  225.                 is an unencoded letter (1 byte), "0" a position-and-length pair
  226.                 (2 bytes). Thus, eight units require at most 16 bytes of code.*/
  227.  
  228.         code_buf_ptr = mask = 1;
  229.  
  230.         s = 0;  r = N - F;
  231.  
  232.         for (i = s; i < r; i++)
  233.                 text_buf[i] = ' ';  /* Clear the buffer with
  234.                                                         any character that will appear often. */
  235.  
  236.         for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
  237.                 text_buf[r + len] = c;  /* Read F bytes into the last F bytes of
  238.                                                                 the buffer */
  239.  
  240.         if ((textsize = len) == 0)
  241.                 return;  /* text of size zero */
  242.  
  243.         for (i = 1; i <= F; i++)
  244.                 InsertNode(r - i);  /* Insert the F strings,
  245.                         each of which begins with one or more 'space' characters.  Note
  246.                         the order in which these strings are inserted.  This way,
  247.                         degenerate trees will be less likely to occur. */
  248.  
  249.         InsertNode(r);  /* Finally, insert the whole string just read.  The
  250.                                         global variables match_length and match_position are set. */
  251.  
  252.         do
  253.         {
  254.                 if (match_length > len)
  255.                         match_length = len;  /* match_length
  256.                                                                 may be spuriously long near the end of text. */
  257.  
  258.                 if (match_length <= THRESHOLD)
  259.                 {
  260.                         match_length = 1;  /* Not long enough match.  Send one byte. */
  261.                         code_buf[0] |= mask;  /* 'send one byte' flag */
  262.                         code_buf[code_buf_ptr++] = text_buf[r];  /* Send uncoded. */
  263.                 }
  264.                 else
  265.                 {
  266.                         code_buf[code_buf_ptr++] = (unsigned char) match_position;
  267.                         code_buf[code_buf_ptr++] = (unsigned char)
  268.  
  269.                 /* Send position and length pair. Note match_length > THRESHOLD. */
  270.                 (((match_position >> 4) & 0xf0) | (match_length - (THRESHOLD + 1)));
  271.                 }
  272.  
  273.                 if ((mask <<= 1) == 0)    /* Shift mask left one bit. */
  274.                 {
  275.                         for (i = 0; i < code_buf_ptr; i++)  /* Send at most 8 units of */
  276.                                 putc(code_buf[i], outfile);     /* code together */
  277.  
  278.                         codesize += code_buf_ptr;
  279.                         code_buf[0] = 0;
  280.                         code_buf_ptr = mask = 1;
  281.                 }
  282.  
  283.                 last_match_length = match_length;
  284.                 for (i = 0; i < last_match_length && (c = getc(infile)) != EOF; i++)
  285.                 {
  286.                         DeleteNode(s);          /* Delete old strings and */
  287.                         text_buf[s] = c;        /* read new bytes */
  288.                         if (s < F - 1)
  289.                                 text_buf[s + N] = c;  /* If the position is
  290.                                                         near the end of buffer, extend the buffer to make
  291.                                                         string comparison easier. */
  292.  
  293.                         s = (s + 1) & (N - 1);
  294.                         r = (r + 1) & (N - 1);
  295.                         /* Since this is a ring buffer, increment the position modulo N. */
  296.  
  297.                         InsertNode(r);  /* Register the string in text_buf[r..r+F-1] */
  298.                 }
  299.  
  300.                 if ((textsize += i) > printcount)
  301.                 {
  302.                         printf("%12ld\r", textsize);
  303.                         printcount += 1024;
  304.                         /* Reports progress each time the textsize exceeds
  305.                            multiples of 1024. */
  306.                 }
  307.  
  308.                 while (i++ < last_match_length)
  309.                 {                                                                                       /* After the end of text, */
  310.                         DeleteNode(s);                                                  /* no need to read, but */
  311.  
  312.                         s = (s + 1) & (N - 1);  r = (r + 1) & (N - 1);
  313.  
  314.                         if (--len)
  315.                                 InsertNode(r);               /* buffer may not be empty. */
  316.                 }
  317.         } while (len > 0);      /* until length of string to be processed is zero */
  318.  
  319.         if (code_buf_ptr > 1)   /* Send remaining code. */
  320.         {
  321.                 for (i = 0; i < code_buf_ptr; i++)
  322.                         putc(code_buf[i], outfile);
  323.                 codesize += code_buf_ptr;
  324.         }
  325.  
  326.         printf("In : %ld bytes\n", textsize);   /* Encoding is done. */
  327.         printf("Out: %ld bytes\n", codesize);
  328.         printf("Out/In: %.3f\n", (double)codesize / textsize);
  329. }
  330.  
  331. void Decode()       /* Just the reverse of Encode(). */
  332. {
  333.         int  i, j, k, r, c;
  334.         unsigned int  flags;
  335.  
  336.         for (i = 0; i < N - F; i++)
  337.                 text_buf[i] = ' ';
  338.  
  339.         r = N - F;
  340.         flags = 0;
  341.  
  342.         for ( ; ; )
  343.         {
  344.                 if (((flags >>= 1) & 256) == 0)
  345.                 {
  346.                         if ((c = getc(infile)) == EOF)
  347.                                 break;
  348.                         flags = c | 0xff00;             /* uses higher byte cleverly */
  349.                 }                                   /* to count eight */
  350.  
  351.                 if (flags & 1)
  352.                 {
  353.                         if ((c = getc(infile)) == EOF)
  354.                                 break;
  355.                         putc(c, outfile);
  356.                         text_buf[r++] = c;
  357.                         r &= (N - 1);
  358.                 }
  359.                 else
  360.                 {
  361.                         if ((i = getc(infile)) == EOF)
  362.                                 break;
  363.                         if ((j = getc(infile)) == EOF)
  364.                                 break;
  365.                         i |= ((j & 0xf0) << 4);
  366.                         j = (j & 0x0f) + THRESHOLD;
  367.                         for (k = 0; k <= j; k++)
  368.                         {
  369.                                 c = text_buf[(i + k) & (N - 1)];
  370.                                 putc(c, outfile);
  371.                                 text_buf[r++] = c;
  372.                                 r &= (N - 1);
  373.                         }
  374.                 }
  375.         }
  376. }
  377.  
  378. void usage()
  379.  
  380. {
  381.         CLEAR;
  382.         printf("filecmpr: Four Arguments are required as exemplified:\n");
  383.         printf("'filecmpr c file1 file2' compresses file1 into file2.\n");
  384.         printf("'filecmpr d file2 file1' decompresses file2 into file1.\n");
  385.         BELL;
  386. }
  387.  
  388. arg_check(argc, argv)
  389. int  argc;
  390. char *argv[];
  391. {
  392.     if (argc != 4)
  393.     {
  394.         usage();
  395.         return(-1);
  396.     }
  397.  
  398.     if ( strpbrk(argv[1], "DCdc") == NULL )
  399.     {
  400.         usage();
  401.         return(-1);
  402.     }
  403.  
  404.     if ( (strcmp(argv[3],argv[2]) == 0)  &&  (strpbrk(argv[1], "Cc") != NULL) )
  405.     {
  406.         CLEAR;
  407.         printf("file_compress: Cannot compress a file onto itself.\n");
  408.         BELL;
  409.         return(-1);
  410.      }
  411.  
  412.      return(0);
  413.  
  414. }
  415.  
  416. main(argc, argv)
  417. int  argc;
  418. char *argv[];
  419. {
  420.         char  *to_file;
  421.         char  cmnd[100], real_to_file_name[15];
  422.         short overlay_file = 0;
  423.  
  424.         if (arg_check(argc, argv))
  425.                 exit(-1);
  426.  
  427.         if ( strcmp(argv[3],argv[2]) == 0 )
  428.         {
  429.                 overlay_file = 1;
  430.                 to_file = "interim_file";
  431.                 strcpy(real_to_file_name,argv[3]);
  432.         }
  433.         else
  434.                 to_file = argv[3];
  435.  
  436.  
  437.         if (( infile  = fopen(argv[2], "r+b")) == NULL )
  438.         {
  439.                 CLEAR;
  440.                 printf("file_compress: unable to open from file %s\n", argv[2]);
  441.                 BELL;
  442.                 return(-1);
  443.         }
  444.  
  445.     if (( outfile = fopen(to_file, "w+b")) == NULL )
  446.         {
  447.                 CLEAR;
  448.                 printf("file_compress: unable to open to file %s\n", to_file);
  449.                 BELL;
  450.                 return(-1);
  451.         }
  452.  
  453.     if (toupper(*argv[1]) == 'C')
  454.         {
  455.                 printf("\n-->Compressing %s into %s<--\n", argv[2], to_file);
  456.                 Encode();
  457.         }
  458.     else
  459.         {
  460.                 printf("\n-->Uncompressing %s<--\n", to_file);
  461.                 Decode();
  462.         }
  463.  
  464.         fclose(infile);
  465.         fclose(outfile);
  466.  
  467.         if ( overlay_file == 1 )
  468.         {
  469. #ifdef DOS
  470.                 sprintf(cmnd,"copy interim_file %s", real_to_file_name);
  471. #else
  472.                 sprintf(cmnd,"mv interim_file %s", real_to_file_name);
  473. #endif
  474.                 system(cmnd);
  475. #ifdef DOS
  476.                 system("del interim_file");
  477. #endif
  478.         }
  479.  
  480.         return(0);
  481. }
  482.